package linkedList.递归;

import linkedList.BaseLinkedListTest;

/**
 * @author songZiHao
 * @version 1.0.0
 * @ClassName 复制带随机指针的链表138.java
 * @Description  https://leetcode-cn.com/problems/copy-list-with-random-pointer/
 * 给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点
 * @createTime 2021年03月11日 13:38:00
 */
public class 复制带随机指针的链表138 extends BaseLinkedListTest {
    public static class Node {
        int val;
        Node next;
        Node random;

        public Node(int val) {
            this.val = val;
            this.next = null;
            this.random = null;
        }
    }

    public static void main(String[] args) {
        Node node = new Node(1);
        Node node1 = new Node(2);
        Node node2 = new Node(3);
        Node node3 = new Node(4);
        node.random = node3;
        node1.random = null;
        node2.random = node1;
        node3.random = node2;
        node.next = node1;
        node1.next = node2;
        node2.next = node3;
        Node list = copyRandomList(node);
        System.out.println(list);
    }

    public static Node copyRandomList(Node head) {
        //todo 在每个节点后面复制一个相同的节点 A->B-C  复制后  A->A->B->B->C->C
        Node p = head;
        copy(p);
        //todo 将每个复制的节点的random指向前一个节点的random指向节点的后一个节点
        p = head;
        while (p != null) {
            if (p.random != null) {
                p.next.random = p.random.next;
            }
            p = p.next.next;
        }
        //todo 分割两个链表
        return separate(head);
    }

    private static Node separate(Node copy) {
        if (copy == null) {
            return null;
        }
        copy.next = separate(copy.next.next);
        return copy;
    }

    private static Node copy(Node head) {
        if (head == null) {
            return head;
        }
        Node copy = copy(head.next);
        Node temp = new Node(head.val);
        head.next = temp;
        temp.next = copy;
        return head;
    }


}
